package mess;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_22 {
    public static void main(String[] args) {
        System.out.println(generateParenthesis(9));
    }
    private static List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backTrick(res, "", 0, 0, n);
        return res;
    }
    private static void backTrick(List<String> res, String str, int countL, int countR, int n){
        if (countL < countR)
            return;
        if (str.length() == 2 * n && countL == countR){
            res.add(str);
            return;
        }
        if (countL <= n ){
            backTrick(res, str + "(", countL + 1, countR, n);
            backTrick(res, str + ")", countL, countR + 1, n);
        }
    }
}
